//
//  LetterCombinations.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/8/26.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  17. 电话号码的字母组合

import UIKit

/*
 17. 电话号码的字母组合
 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。



 示例:

 输入："23"
 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 */

class LetterCombinations: NSObject {

    var sourceHash:[String:[String]] = [:]
    var resultArr:[String] = []
    
    func letterCombinations(_ digits: String) -> [String] {
        guard digits.count != 0 else{
            return []
        }
        
        sourceHash = ["2":["a","b","c"],
                      "3":["d","e","f"],
                      "4":["g","h","i"],
                      "5":["j","k","l"],
                      "6":["m","n","o"],
                      "7":["p","q","r","s"],
                      "8":["t","u","v"],
                      "9":["w","x","y","z"]]

        
        self.dfs(0, digits, [])
        return resultArr
    }
    
    func dfs(_ startIndex: Int, _ digits: String,_ tmpArr: [String]){
        var tmpArr = tmpArr
        if startIndex == digits.count{
            resultArr.append(tmpArr.joined(separator: ""))
            return
        }
        let arr = Array(digits)
        let digit = String(arr[startIndex])
        
        let lettrtArr = sourceHash[digit]
        for i in 0 ..< lettrtArr!.count{
            tmpArr.append(lettrtArr![i])
            self.dfs(startIndex+1, digits, tmpArr)
            tmpArr.removeLast()
        }
    }
}
